#leetcode题目32：最长有效括号
#难度：困难
#时间复杂度：O(n)
#空间复杂度：O(n)
#方法：动态规划

#来源于第二个视频合集

class Solution:
    #方法1：ai解法，动态规划
    # def longestValidParentheses(self, s: str) -> int:
    #     if not s:
    #         return 0
    #     dp=[0]*len(s)
    #     for i in range(1,len(s)):
    #         if s[i]==")":
    #             if s[i-1]=="(":
    #                 dp[i]=dp[i-2]+2
    #             elif s[i-1]==")" and i-dp[i-1]-1>=0 and s[i-dp[i-1]-1]=="(":
    #                 dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2]
    #     return max(dp)

    #方法2：视频解法，经典栈解法
    def longestValidParentheses(self, s: str) -> int:
        stack=[]
        res=0
        for i in range(len(s)):
            if not stack or s[i]=="(" or s[stack[-1]]==")":
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    cur=i+1
                else:
                    cur=i-stack[-1]
                res=max(res,cur)

        return res



#测试数据
s="(()"
#预期输出：2
solution=Solution()
print(solution.longestValidParentheses(s))  

s=")()())"
#预期输出：4
solution=Solution()
print(solution.longestValidParentheses(s))  

s=""
#预期输出：0
solution=Solution()
print(solution.longestValidParentheses(s))  
